%%%-------------------------------------------------------------------
%%% File    : p15.erl
%%% Author  : Plamen Dragozov <plamen at dragozov.com>
%%% Description : 
%%% Starting in the top left corner of a 2×2 grid, 
%%% there are 6 routes (without backtracking) to the bottom right corner.
%%% How many routes are there through a 20×20 grid?
%%% Created :  4 Dec 2008
%%%-------------------------------------------------------------------
-module(p15).

%% API
-compile(export_all).

%%====================================================================
%% API
%%====================================================================

%There are actually N+1 nodes in a grid of size N. 
%The number of routes of a node is equal to the sum of the routes of
%its neighbour nodes that are closer to the end. Border nodes have 1
%neighbour (which is also a border node, so they have 1 route), while 
%all the rest have 2 neighbours.

%%--------------------------------------------------------------------
%% Function: solution()
%% Description:
%%--------------------------------------------------------------------
solution(Size) ->
    node(1, 1, Size + 1, ets:new(lookup, [])).

%%====================================================================
%% Internal functions
%%====================================================================
%Returns the number of routes from the given node, uses a lookup
%table for repeated nodes.
%border node, has 1 route
node(I, J, Size, _) when (I =:= Size andalso J =:= Size - 1) orelse (I =:= Size - 1 andalso J =:= Size) -> 1;
%normal node
node(I, J, Size, LookupTable) ->
    P = ets:lookup(LookupTable, {I, J}),
    case  P of
        [] ->
            Routes1 = case I < Size of
                     true ->
                         node(I + 1, J, Size, LookupTable);
                     _ -> 0
                 end,
            Routes2 = case J < Size of
                     true ->
                         node(I, J + 1, Size, LookupTable);
                     _ -> 0
                 end,
            Routes = Routes1 + Routes2,
            ets:insert(LookupTable, {{I, J}, Routes}),
            Routes;
        [{_, Routes}] -> Routes
    end.

